1451. Симметрия точек

На плоскости задано n разных точек P₁, P₂, …, P_n. своими координатами (x_i, y_i), i = 1, …, n. Преобразование S производится следующим образом: для каждой точки X₀ плоскости сначала строится точка X₁, симметричная ей относительно P₁, потом строится точка X₂, симметричная X₁ относительно P₂, и так далее пока не будет построена точка X_n, симметричная X_n-1 относительно P_n. Если при описанном преобразовании S существует единственная точка, которая не изменяет своих координат (неподвижная точка), то вывести ее координаты. Если существует более одной неподвижной точки, то вывести 0. Если неподвижных точек не существует, вывести -1.

Вход. Первая строка содержит количество точек n. Следующие n строк содержат целочисленные координаты точек (x_i, y_i), i = 1, …, n.

Выход. Вывести координаты неподвижной точки (x, y), если она единственна. Если существует более одной неподвижной точки, то вывести 0. Если неподвижных точек не существует, вывести -1.

Пример входа

Sample 1

4

0 0

0 1

1 1

1 0

Sample 2

3

0 0

0 1

1 0

Sample 3

4

0 0

1 0

0 1

100 100

Пример выхода

Sample 1

0

Sample 2

1 -1

Sample 3

-1

РЕШЕНИЕ

геометрия

Анализ алгоритма

Точка с координатами (x, y) при симметрии относительно точки (p₁, q₁) переходит в точку (2p₁ – x, 2q – y₁). Если полученную точку симметрически отобразить относительно (p₂, q₂), то получим точку (2p₂ – 2p₁ + x, 2q₂ – 2q₁ + y). Продолжая процедуру отображения n раз, в конце получим точку с координатами (2p_n– 2p_n-1 + 2p_n-2 – … + (-1)ⁿx, 2q_n– 2q_n-1 + 2q_n-2 – … + (-1)ⁿy). Ее координаты должны совпадать с координатами исходной точки, то есть

x = 2p_n – 2p_n-1 + 2p_n-2 – … + (-1)ⁿx

y = 2q_n– 2q_n-1 + 2q_n-2 – … + (-1)ⁿy

Для нахождения координат искомой неподвижной точки (x, y) достаточно решить систему двух линейных уравнений. Если n нечетно, то система всегда имеет единственное решение:

x = p_n – p_n-1 + p_n-2 – … + p₁

y = q_n – q_n-1 + q_n-2 – … + q₁

При четном n переменные x и y сокращаются, и оба уравнения превращаются в равенства:

0 = p_n – p_n-1 + p_n-2 – … – p₁

0 = q_n – q_n-1 + q_n-2 – … – q₁

Если оба равенства истины, то любая точка плоскости является неподвижной. Если хотя бы одно равенство не верно, то неподвижных точек не существует.

Реализация алгоритма

В переменной pp будем вычислять значение p₁ – p₂ + p₃ – … + (-1)ⁿp_n, а в переменной qq значение q₁ – q₂ + q₃ – … + (-1)ⁿq_n.

scanf("%d",&n);

pp = qq = 0; dir = 1;

for(i = 0; i < n; i++)

{

scanf("%d %d",&p, &q);

pp += p * dir; qq += q * dir;

dir = -dir;

}

Если n нечетно, то выводим неподвижную точку (pp, qq).

if (n % 2) printf("%d %d\n",pp,qq);else

{

Если n четно, то лишь при (pp, qq) = (0, 0), то любая точка плоскости является неподвижной. Если хотя бы одно из значений pp или qq отлично от нуля, то неподвижных точек нет.

if (pp || qq) printf("-1\n");

else printf("0\n");

}